package main

import (
	"fmt"
)

/*
给定一颗二叉搜索树，请找出其中的第k小的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

思路：递归的方式：二叉搜索树的中序遍历就是排序的，所以用中序遍历，每一次中间的时候判断是否等于k即可。

         非递归的方式：运用栈进行操作。相当于用栈实现了中序遍历，在中间进行了个数的判断
*/

type TreeNode struct {
	val       int
	leftNode  *TreeNode
	rightNode *TreeNode
}

func main() {
	root := TreeNode{val: 8}
	root.leftNode = &TreeNode{val: 3}
	root.rightNode = &TreeNode{val: 10}
	root.leftNode.leftNode = &TreeNode{val: 1}
	root.leftNode.rightNode = &TreeNode{val: 6}
	root.leftNode.rightNode.leftNode = &TreeNode{val: 4}
	root.leftNode.rightNode.rightNode = &TreeNode{val: 7}
	root.rightNode.rightNode = &TreeNode{val: 14}
	root.rightNode.rightNode.leftNode = &TreeNode{val: 13}

	fmt.Println(KthNode(&root, 3))
}

/*
1：中序遍历二叉搜索树即可得到从小到大的顺序
*/
var count int

func KthNode(pRoot *TreeNode, k int) *TreeNode {
	if pRoot == nil {
		return nil
	}

	leftNode := KthNode(pRoot.leftNode, k)
	if leftNode != nil {
		return leftNode
	}
	count++
	if count == k {
		return pRoot
	}
	rightNode := KthNode(pRoot.rightNode, k)
	if rightNode != nil {
		return rightNode
	}

	return nil
}
